package com.muchfish.algorithm.queue;


import com.muchfish.algorithm.linkedlist.pojo.ListNode;

/**
 * <a href="https://leetcode.cn/problems/design-circular-queue/description/">题目：622. 设计循环队列</a>
 * <br>
 * 题目描述：<br>
 * 设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。<br>
 * 循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。<br>
 * <br>
 * 解题思路： <br>
 * 方法一：数组<br>
 * <img src="https://assets.leetcode-cn.com/solution-static/622/622_1.png"><br>
 * 循环队列的属性如下:<br>
 * elements：一个固定大小的数组，用于保存循环队列的元素。<br>
 * capacity：循环队列的容量，即队列中最多可以容纳的元素数量。<br>
 * front：队列首元素对应的数组的索引。<br>
 * rear：队列尾元素对应的索引的下一个索引。<br>
 * <br>
 */
public class Queue1 {
}

class MyCircularQueue {
    private int front;
    private int rear;
    private int capacity;
    private int[] elements;

    public MyCircularQueue(int k) {
        capacity = k + 1;
        elements = new int[capacity];
        rear = front = 0;
    }

    /**
     * 添加元素
     * 队尾赋值，再往前走一格并fu代表添加元素
     *
     * @param value
     * @return
     */
    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
        }
        elements[rear] = value;
        rear = (rear + 1) % capacity;
        return true;
    }

    /**
     * 删除队首元素
     * front往前走一格代表删除队首元素
     *
     * @return
     */
    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        }
        front = (front + 1) % capacity;
        return true;
    }

    /**
     * 获取队首元素
     *
     * @return
     */
    public int Front() {
        if (isEmpty()) {
            return -1;
        }
        return elements[front];
    }

    /**
     * 获取队尾元素
     *
     * @return
     */
    public int Rear() {
        if (isEmpty()) {
            return -1;
        }
        return elements[(rear - 1 + capacity) % capacity];
    }

    public boolean isEmpty() {
        return rear == front;
    }

    public boolean isFull() {
        return ((rear + 1) % capacity) == front;
    }
}

class MyCircularQueue2 {
    private ListNode head;
    private ListNode tail;
    private int capacity;
    private int size;

    public MyCircularQueue2(int k) {
        capacity = k;
        size = 0;
    }

    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
        }
        ListNode node = new ListNode(value);
        if (head == null) {
            head = tail = node;
        } else {
            tail.next = node;
            tail = node;
        }
        size++;
        return true;
    }

    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        }
        ListNode node = head;
        head = head.next;
        size--;
        return true;
    }

    public int Front() {
        if (isEmpty()) {
            return -1;
        }
        return head.val;
    }

    public int Rear() {
        if (isEmpty()) {
            return -1;
        }
        return tail.val;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == capacity;
    }
}
